Generally, as compared with a processing speed for a CPU or host, a data write and read speed between the CPU or host and an external main storage medium is low. However the capability for the CPU or host is improved, therefore, the data write and read speed with the external main storage medium becomes a bottleneck for effecting on a high speed trend of the overall system.
In order to solve the problem, in the prior art, a local cache memory is provided between the CPU and the external main storage medium. Although the cache memory has a low capacity than the external main storage medium, a write and read can be performed in a higher speed in the cache memory. An overall processing speed can be improved by storing data read ever from the external main storage medium thereat.
Generally, the data write and read between the CPU and the external main storage medium are performed in a data unit composed of multiple bytes, that is, in a unit such as a block or a line. The block has an address composed of multiple bits, which is a data address for data in the external main storage medium.
As an example for the data write and read between the cache memory and the external main storage medium, it adopts an n-Way Set Associative mode in a Japanese patent (Publication number 2004-38807). As disclosed in the publication, the cache memory is composed of multiple ways, each of which is composed of multiple blocks. Moreover, an index of location for each of the blocks in the way is given to each of the blocks in the way. As for the cache memory, a few lower bits a1 of the data address for the data are used as the index, and a few upper bits a2 are used as an identifier for the data. Therefore, the block in the cache memory is made in correspondence with the data in the external main storage medium, on a basis of the data address for the external main storage medium.
In the method, the data having the same few lower bits a1 of the address, i.e., the data having the same index, can be placed in different ways. A number of the data having the same index as many as the number of the ways can be placed. If new data having the same index beyond the number of the ways is to be placed, however, data are selected and deleted from the data having the same index placed in the respective ways, by using a method such as LRU (Least Recently Used), and is then replaced with the new data. At this time, even though there is an empty block in other index space or spaces, it is impossible to place the new data thereat since the few low bits a1 of the data address for the data in the external main storage medium are assigned to a specific index in the cache memory, and are limited to such a place. In the method, even though there is an empty place in view of the overall cache memory, a condition that the data in the cache memory has to be deleted in order to place the new data would occur, causing a reduced utilization ratio for the storage space of the cache memory.
As another method, all of the blocks in the cache memory can be used as the ways. Therefore, the data in the external main storage medium will not be limited to the specific place in the cache memory, so that all of the data can be placed on any place in the cache memory. On condition of the same capacity for the cache memory and the same capacity for the block, as compared with the aforementioned method, a processing time upon querying an identifier would be dramatically increased due to a dramatic increase of the number of the identifiers in this method.